/*
 * Colussi.cpp
 *
 *  Created on: 12-08-2013
 *      Author: Krzychu
 */

#include "Colussi.h"

#include "Config.h"

#include <stdio.h>
#include <string.h>

Colussi::Colussi()
{

}

Colussi::~Colussi()
{

}

std::string Colussi::getName()
{
	return "Colussi";
}

int Colussi::preColussi(std::string pattern, int h[], int next[], int shift[])
{
	int i, k, nd, q, r, s;

	int patternSize = pattern.size();

	int hmax[patternSize], kmin[patternSize], nhd0[patternSize], rmin[patternSize];

	/* Computation of hmax */
	i = k = 1;
	do
	{
		while (pattern[i] == pattern[i - k])
		{
			i++;
		}

		hmax[k] = i;
		q = k + 1;

		while (hmax[q - k] + k < i)
		{
			hmax[q] = hmax[q - k] + k;
			q++;
		}

		k = q;
		if (k == i + 1)
		{
			i = k;
		}
	}
	while (k <= patternSize);

	/* Computation of kmin */
	memset(kmin, 0, patternSize * sizeof(int));

	for (i = patternSize; i >= 1; --i)
	{
		if (hmax[i] < patternSize)
		{
			kmin[hmax[i]] = i;
		}
	}

	/* Computation of rmin */
	for (i = patternSize - 1; i >= 0; --i)
	{
		if (hmax[i + 1] == patternSize)
		{
			r = i + 1;
		}
		if (kmin[i] == 0)
		{
			rmin[i] = r;
		}
		else
		{
			rmin[i] = 0;
		}
	}

	/* Computation of h */
	s = -1;
	r = patternSize;
	for (i = 0; i < patternSize; ++i)
	{
		if (kmin[i] == 0)
		{
			h[--r] = i;
		}
		else
		{
			h[++s] = i;
		}
	}
	nd = s;

	/* Computation of shift */
	for (i = 0; i <= nd; ++i)
	{
		shift[i] = kmin[h[i]];
	}
	for (i = nd + 1; i < patternSize; ++i)
	{
		shift[i] = rmin[h[i]];
	}

	shift[patternSize] = rmin[0];

	/* Computation of nhd0 */
	s = 0;
	for (i = 0; i < patternSize; ++i)
	{
		nhd0[i] = s;
		if (kmin[i] > 0)
		{
			++s;
		}
	}

	/* Computation of next */
	for (i = 0; i <= nd; ++i)
	{
		next[i] = nhd0[h[i] - kmin[h[i]]];
	}
	for (i = nd + 1; i < patternSize; ++i)
	{
		next[i] = nhd0[patternSize - rmin[h[i]]];
	}

	next[patternSize] = nhd0[patternSize - rmin[h[patternSize - 1]]];

	return (nd);
}

searchResult Colussi::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	int i, j, last, nd, h[patternSize], next[patternSize], shift[patternSize];

	/* Processing */
	nd = preColussi(pattern, h, next, shift);

	/* Searching */
	i = j = 0;
	last = -1;
	while (j <= textSize - patternSize)
	{
		result.iterationsTaken++;
		while (i < patternSize && last < j + h[i]
				&& pattern[h[i]] == text[j + h[i]])
		{
			i++;
		}

		if (i >= patternSize || last >= j + h[i])
		{
			result.positionsFound.push_back(j);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}

			i = patternSize;
		}

		if (i > nd)
		{
			last = j + patternSize - 1;
		}

		j += shift[i];
		i = next[i];
	}

	return result;
}

